package meduim.string;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 不重复最长子串的长度
 *
 * @author MaoLin Wang
 * @date 2020/8/169:51
 */
public class LongestSubstring {

//    public static int lengthOfLongestSubstring(String s) {
//        if (s == null || "".equals(s)) {
//            return 0;
//        }
//        if (" ".equals(s) || s.length() == 1) {
//            return 1;
//        }
//        int maxLength = 0;
//        int max = 0;
//        int len = s.length();
//        Map<Character, Integer> set = null;
//
//        int m = 0;
//        int n = 1;
//
//        int index = 0;
//
//        while (true) {
//            if (m == len - 1) {
//                break;
//            }
//            set=null;
//            set = new HashMap<Character, Integer>();
//            char s1 = s.charAt(m);
//            char s2 = s.charAt(n);
//            set.put(s1, m);
//            set.put(s2, n);
//            if (s1 == s2) {
//                m++;
//                n++;
//            } else {
//                maxLength = 2;
//                n++;
//                if (n <= len - 1) {
//                    s2 = s.charAt(n);
//                }else {
//                    if (maxLength>max){
//                        max=maxLength;
//                    }
//                    break;
//                }
//                boolean flag = false;
//                while (!set.containsKey(s2)) {
//                    set.put(s2, n);
//                    maxLength++;
//                    n++;
//                    if (n > len - 1) {
//                        flag = true;
//                        break;
//                    }
//                    s2 = s.charAt(n);
//                }
//
//                if (maxLength > max) {
//                    max = maxLength;
//                }
//                maxLength = 0;
//                int s2Index = set.get(s2);
//                int tempLength = n - s2Index;
//                if (tempLength > max) {
//                    max = tempLength;
//                }
//                if (s2Index == 0) {
//                    m = 1;
//                } else {
//
//                    m = s2Index + 1;
//                }
//                n = m + 1;
//
//                if (flag) {
//                    break;
//                }
//            }
//
//        }
//        if (max == 0) {
//            return 1;
//        }
//        return max;
//
//
//    }
    public static int lengthOfLongestSubstring2(String s) {
        if (s.length()==0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;//最长子串长度
        int left = 0;//滑动窗口左下标，i相当于滑动窗口右下标
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){//charAt() 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。
                left = Math.max(left,map.get(s.charAt(i)) + 1);       //map.get():返回字符所对应的索引，当发现重复元素时，窗口左指针右移
            }        //map.get('a')=0,因为map中只有第一个a的下标，然后更新left指针到原来left的的下一位
            map.put(s.charAt(i),i);      //再更新map中a映射的下标
            max = Math.max(max,i-left+1);     //比较两个参数的大小
        }
        return max;

    }

    public static void main(String[] args) {
        int a = lengthOfLongestSubstring2("abccdabg");
        System.out.println(a);
    }
}
